import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class MyBinaryTree {

    public static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;       

        public TreeNode(int val){
            this.val=val;
        }
    }

    public void preOrder(TreeNode root){ //前
        if(root==null){
            return;
        }
        System.out.print(root.val+" ");
        postOrder(root.left);
        postOrder(root.right);
    }

    public void inOrder(TreeNode root){//中
         if(root==null){
        return;
        }
        inOrder(root.left);
       System.out.print(root.val+" ");
       inOrder(root.right);
    }

    public void postOrder(TreeNode root){//后
    if(root==null){
        return;
    }
    preOrder(root.left);
    preOrder(root.right);
    System.out.print(root.val+" ");
    }

    /*public int NodeSize;

    public void getNodeSize(TreeNode root){//用NodeSize
        if(root==null){
            return;
        }
        NodeSize++;
        getNodeSize(root.right);
        getNodeSize(root.left);
    }*/

    public int getNodeSize(TreeNode root){
        if(root==null)return  0;
        return 1+getNodeSize(root.left)+getNodeSize(root.right);
    }

    /*public int LeafNodeSize;  递归
    public void getLeafNodeCount(TreeNode root){
        if(root==null)return ;
        if(root.left==null&&root.right==null){
            LeafNodeSize++;
            return;
        }
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);
    }*/

    public int getLeafNodeCount(TreeNode root){
        if(root==null)return 0;
        if(root.left==null&&root.right==null)return 1;
        return getLeafNodeCount(root.left)+getLeafNodeCount(root.right);
    }

    public int getKLevelNodeCount(TreeNode root,int k){//第k层的节点个数
        if(root==null)return 0;
        if(k==1)return 1;
        return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);
    }

    public int getHeight(TreeNode root){//二叉树的高度
        if(root==null)return 0;
        int leftHeight=getHeight(root.left);
        int rightHeight=getHeight(root.right);
        if(leftHeight>=rightHeight){
            return 1+leftHeight;
        }else{
            return 1+rightHeight;
        }
    }

    public TreeNode find(TreeNode root,int key){//先序遍历查找元素key
        if(root==null)return null;
        if(root.val==key) return root;
        TreeNode left=find(root.left,key);
        TreeNode right=find(root.right,key);
        if(left!=null)return left;
        if(right!=null)return right;
        return null;
    }

    public void levelOrder(TreeNode root){//层序遍历
        if(root==null) return;
        Queue <TreeNode>queue=new LinkedList();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur=queue.poll();
            System.out.print(cur.val+" ");
            if(cur.left!=null){
                queue.offer(cur.left);
            }
            if(cur.right!=null){
                queue.offer(cur.right);
            }
        }

        System.out.println();
    }

    public List<List<Integer>> levelOrder1(TreeNode root){//可分层 层序遍历
        List<List<Integer>> ret=new ArrayList<>();//用二维顺序表存储每一层的数据，存放顺序表的顺序表
        Queue <TreeNode>queue=new LinkedList();
        if(root==null) return ret;
        queue.offer(root);
        while(!queue.isEmpty()){
            List <Integer> tmp=new ArrayList<>();//存放每一层数据的顺序表
            int size=queue.size();
            while(size!=0){
                TreeNode cur=queue.poll();
                size--;
                tmp.add(cur.val);
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
            }
        ret.add(tmp);
        }
        return  ret;
    }
}
